#include "game.h"
# include <bits/stdc++.h>
using namespace std;
int n;
bool died[5005][5005];
int num[5005];
int tot=0;
vector<int> ans,v,v2;
bool used[5005];
int get(vector<int> v)
{
    int ans=0;
    for(int i=0;i<n;i++)
        ans+=died[i+1][v[i]];
    return ans;
}
int found;
void godie(int i,int j)
{
    died[i][j]=1;
    num[i]++;
    if(num[i]==n-1)
    {
        for(int j=1;j<=n;j++)
            if(!died[i][j])
            {
                ans[i-1]=j;
                break;
            }
        used[ans[i-1]]=1;
        for(int j=1;j<=n;j++)
            if(j!=i && !died[j][ans[i-1]])
                godie(j,ans[i-1]);
        tot++;
    }
}
int fa[5005];
int getfa(int x)
{
    if(fa[x]==x)
        return x;
    return fa[x]=getfa(fa[x]);
}
void merge(int x,int y)
{
    fa[getfa(x)]=getfa(y);
}
vector<int> guess(int nn, int limit)
{
    mt19937 Rnd(time(0));
    n=nn;
	ans.resize(n);
    v.resize(n),v2.resize(n);
    for(int i=0;i<n;i++)
        v[i]=v2[i]=i+1;
    bool reved=1;
    for(int i=1;i<=limit;i++)
    {
        int lsttot=tot;
        if(reved)
            shuffle(v2.begin(),v2.end(),Rnd),reved=0;
        else
            reverse(v2.begin(),v2.end()),reved=1;
        int pos=0;
        for(int i=0;i<n;i++)
            if(num[i+1]==n-1)
                v[i]=ans[i];
            else
                v[i]=v2[pos++];
        int aaa=count(v);
        assert(aaa>=tot);
        if(aaa==tot)
        {
            for(int i=0;i<n;i++)
                if(num[i+1]!=n-1 && !died[i+1][v[i]])
                    godie(i+1,v[i]);
        }
        if(tot!=lsttot)
        {
            v2.clear();
            for(int i=1;i<=n;i++)
                if(!used[i])
                    v2.push_back(i);
        }
        if(tot==n)
            break;
    }
	return ans;
}
